package interview.huawei.tjt.training.huisu;

import java.util.*;

/**
 * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
 *
 * 示例:
 *
 * 输入: [4, 6, 7, 7]
 * 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
 * 说明:
 *
 * 给定数组的长度不会超过15。
 * 数组中的整数范围是 [-100,100]。
 * 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
 */
public class FindSubsequences {

    private static List<LinkedList<Integer>> result = new ArrayList();
    private static LinkedList<Integer> path = new LinkedList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] str = sc.nextLine().split(",");
            int[] nums = new int[str.length];
            for (int i = 0; i < str.length; i ++) {
                if (!str[i].equals("") && str[i] != null) {
                    nums[i] = Integer.parseInt(String.valueOf(str[i]));
                }
            }
            Arrays.sort(nums);  // 要先拍下序，要不然得不到想要的结果
            helper(nums, 0);
            System.out.println(result);
        }
    }

    private static void helper (int[] nums, int startIndex) {
        // 结束条件
        if (path.size() <= nums.length && path.size() >= 2) {
            if (!result.contains(path)) {
                result.add(new LinkedList<>(path));
            }
        }

        for (int i = startIndex; i < nums.length; i ++) {
//            if (path.size() > nums.length) break;
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) continue;
            path.add(nums[i]);
            helper(nums, i);
            path.removeLast();
        }
    }

}
